This invention relates to programmable probability processing.
One approach to inference-based computation (e.g., Belief Propagation, BP) makes use of factor graphs, for instance, as described in Loeliger, “Introduction to Factor Graphs,” IEEE Signal Processing Magazine, January 2004. One graph-based inference approach is the Sum-Products (SP) approach, as described in the referenced paper. Another approach is the Min-Sum (MS) approach (also referred to as Max-Sum or Max-Product), which can be regarded as an approximation of the SP approach. A description of such algorithms may be found in H. Wymeersch, Iterative Receiver Design, Cambridge University Press, Cambridge, 2007.
Referring to FIG. 1, an example of a portion of a factor graph 100 includes factor nodes 110-111 and variable nodes 121-123. Factor node 110 implements a factor (e.g., a constraint) that depends on the variables A, B, and C associated with variable nodes 121-123, respectively. In the SP approach, the factor node 110 receives messages from the adjacent variable nodes, and uses those messages to compute and emit output messages back to the variable nodes. In the SP approach, we use the notation {right arrow over (μ)}A (or more explicitly {right arrow over (μ)}A→F) to represent the message from the variable node 121 associated with variable A to factor node 110 associated with factor F. Similarly, the message passing back to the variable node is represented as A (or more explicitly A←F. For the factor graph shown in FIG. 1, the messages for factor node 110 are computed as follows:
                                                        μ              ←                        C                    ⁡                      (            c            )                          =                              ∑                          a              ,              b                                ⁢                                          ⁢                                    w              ⁡                              (                                  a                  ,                  b                  ,                  c                                )                                      ⁢                                                            μ                  →                                A                            ⁡                              (                a                )                                      ⁢                                                            μ                  →                                B                            ⁡                              (                b                )                                                                        (                  1          ⁢                                          ⁢          a                )                                                                    μ              ←                        B                    ⁡                      (            b            )                          =                              ∑                          a              ,              c                                ⁢                                          ⁢                                    w              ⁡                              (                                  a                  ,                  b                  ,                  c                                )                                      ⁢                                                            μ                  →                                A                            ⁡                              (                a                )                                      ⁢                                                            μ                  →                                C                            ⁡                              (                c                )                                                                        (                  1          ⁢                                          ⁢          b                )                                                                    μ              ←                        A                    ⁡                      (            a            )                          =                              ∑                          b              ,              c                                ⁢                                          ⁢                                    w              ⁡                              (                                  a                  ,                  b                  ,                  c                                )                                      ⁢                                                            μ                  →                                B                            ⁡                              (                b                )                                      ⁢                                                            μ                  →                                C                            ⁡                              (                c                )                                                                        (                  1          ⁢                                          ⁢          c                )            
The weights w(a,b,c) represent the factor, for example, as a probability distribution with all the values adding up to 1.0, of as another form of distribution, or as 0/1 indicator values.
In the Max-Product approach, the summations are effectively replaced with max operations. The Min-Sum approach is effectively a logarithmic version of the Max-Product approach. The messages represent logarithmic messages, for instance, defined as {right arrow over (l)}A≡−log({right arrow over (μ)}A) (taking the logarithm element-wise). Similarly, the weights are defined as W(a,b,c)=−log w(a,b,c). For the MS approach, the messages are computed as follows:C(c)=mina,b(W(a,b,c)+{right arrow over (l)}A(a)+{right arrow over (l)}B(b))   (2a)B(b)=mina,c(W(a,b,c)+{right arrow over (l)}A(a)+{right arrow over (l)}C(c))   (2b)A(a)=minb,c(W(a,b,c)+{right arrow over (l)}B(b)+{right arrow over (l)}C(c))   (2c)
In the discussion below, we use the notation |A| to represent the number of values that the variable A can take on. In this notation, the number of terms in the sum for C(c) is |A|×|B|. For instance, if each variable can take on one of 64 values, there are 4096 terms in the sum or min, which must be computed for each of the 64 output values, for a total of over 0.78 million terms to compute three output messages.
There is a need to accelerate computation of the messages for the purpose of accelerating inference computation, for example, based on factor graphs.